The PC-SIG Library 9/The PC-SIG Library on CD ROM - Ninth Edition.iso/501_600/DISK0579/DISK0579.ZIP/CHAP12.TXT

Text File | 1989-12-01 | 28KB | 650 lines

                                                   Chapter 12
                              POINTERS AND DYNAMIC ALLOCATION


THIS IS ADVANCED MATERIAL
____________________________________________________________

For certain types of programs, pointers and dynamic allocation
can be a tremendous advantage, but many programs do not need
such a high degree of data structure.  For that reason, it
would probably be to your advantage to lightly skim over these
topics and come back to them later when you have a substantial
base of Pascal programming experience.  It would be good to
at least skim over this material rather than completely
neglecting it, so you will have an idea of how pointers and
dynamic allocation work and that they are available for your
use when needed.

A complete understanding of this material will require deep
concentration as it is complex and not at all intuitive.
Nevertheless, if you pay close attention, you will have a good
grasp of pointers and dynamic allocation in a short time.


WHAT ARE POINTERS, AND WHAT GOOD ARE THEY?
____________________________________________________________

Examine the program named POINT.PAS for     =================
your first example of a program using           POINT.PAS
pointers.  In the var declaration you will  =================
see two variables named Where and Who that
have the symbol ^ in front of their types.
This defines them, not as variables, but as pointers to
integer type variables and since they are pointers, they store
an address.  Figure 12-1 is a graphical representation of the
data space prior to beginning execution of the program.  A box
represents a variable, and a box with a dot in it represents
a pointer.  In line 12 of the program, the variable Index is
assigned the value of 17 for purposes of illustration.  The
pointer named Where is then assigned the address of the
variable Index which means that it does not contain the value
of 17, it contains the address of the storage location where
the variable Index is stored.  In like manner, we assign the
address of Index to the pointer named Who.  It should be
obvious to you that Addr is a TURBO Pascal function that
returns the address of its argument.


HOW DO WE USE THE POINTERS?
____________________________________________________________

It should be clear to you that we now have a single variable
named Index with two pointers pointing at it as depicted in
figure 12-2.  If the pointers are useful, we should be able

                                                    Page 12-1

                              Pointers and Dynamic Allocation

to do something with them now, so we simply print out the same
variable three different ways in line 15.  When we write
"Where^", we are telling the system that we are not interested
in the pointer itself but instead we are interested in the
data to which the pointer points.  This is referred to as
dereferencing the pointer.  Careful study of the output fields
in line 15 will reveal that we first display the value of
Index, then the value to which the pointer Where points, and
finally the value to which the pointer Who points.  Since both
pointers point to the variable Index, we are essentially
displaying the value of Index three times.  You will confirm
this when you compile and run this program.

In line 17, we tell the system to assign the value of 23 to
the variable to which the pointer Where points as an
illustration and figure 12-3 pictures the data space at this
time.  If you understood the discussion in the previous
paragraph, you will understand that we are actually assigning
the variable named Index the value of 23 because that is where
the pointer named Where is pointing.  In line 18, we once
again display the value of the variable Index 3 times just as
we did in line 15.  It would be to your advantage to compile
and run this program to see that the value of 17 is output
three times, then the value of 23 is output three times.

In a program as simple as this, the value of pointers is not
at all clear but a simple program is required in order to make
the technique clear.  Display the program named POINT.PAS on
your monitor again because we are not yet finished with it.


A FEW MORE POINTERS
____________________________________________________________

In line 4, we define a new type named Int_Point which is a
pointer type to an integer variable.  We use this new type in
line 9 to define three more pointers and in line 20, we assign
one of them the address of the variable named Index.  Since
the pointers are of identical types, in line 21 we can assign
Pt2 the value of Pt1, which is actually the address of the
variable named Index.  Likewise, the pointer Pt3 is assigned
the value of Pt2, and we have all three pointers pointing to
the variable named Index.  If you are using TURBO Pascal
version 4.0 or 5.x, you are allowed to assign pointers like
this only if they have the same type, which these three do.
However, since the pointers named Where and Who are declared
individually, they are not of the same type according to the
rules of Pascal and if line 14 were changed to read "Who :=
Where;", a compilation error would occur with TURBO Pascal
version 4.0 or 5.x.  This error would not occur with TURBO
Pascal 3.0 since it is a little less stringent in its type
checking.  The variables are only assignment compatible if
they are declared with the same type name.


                                                    Page 12-2

                              Pointers and Dynamic Allocation

Finally, we assign the only variable in this program which is
named Index the value of 151 in line 23 and display the value
151 three times as we did above.  Compile and run this program
again to see that it does indeed display the value 151 three
times.


THIS IS FOR TURBO PASCAL VERSION 4.0 OR 5.X
____________________________________________________________

If you are using TURBO Pascal version 4.0    ================
or 5.x, you should display the program          POINT4.PAS
named POINT4.PAS on your monitor for an      ================
example of another new extension to the
Pascal programming language by Borland.
This program is identical to the last except in lines 13, 14
and 20, where the symbol @ is used to denote the address of
the variable Index rather than the function Addr.  This is
only available with TURBO Pascal version 4.0 or 5.x as a
convenience to you.  In ANSI standard Pascal the @ symbol is
used as a synonym for the ^ symbol but Borland chose to use
it for a completely different purpose.  If you are using TURBO
Pascal 3.0, you will not be able to compile and run this
program, but nothing is lost because it is identical to the
previous one.


OUR FIRST LOOK AT DYNAMIC ALLOCATION
____________________________________________________________

If you examine the file named                ================
POINTERS.PAS, you will see a very trivial      POINTERS.PAS
example of pointers and how they are used    ================
with dynamically allocated variables.  In
the var declaration, you will see that the
two variables have a ^ in front of their respective types once
again, defining two pointers.  They will be used to point to
dynamically allocated variables that have not yet been
defined.

The pointer My_Name is a pointer to a 20 character string.
The pointer actually points to an address somewhere within the
computer memory, but we don't know where yet.  Actually, there
is nothing for it to point at because we have not defined a
variable.  After we assign it something to point to, we can
use the pointer to access the data stored at that address.

Your computer has some amount of memory installed in it. If
it is an IBM-PC or compatible, it can have up to 640K of RAM
which is addressable by various programs.  The operating
system requires about 60K of the total, and the TURBO Pascal
run time system requires about 4K to 8K depending on which
version you are using, and what functions you have called.
The TURBO Pascal program can use up to 64K.  Adding those

                                                    Page 12-3

                              Pointers and Dynamic Allocation

three numbers together results in about 128K or 132K.  Any
memory you have installed in excess of that is available for
the stack and the heap.  The stack is a standard area defined
and controlled by DOS that can grow and shrink as needed.
Many books are available to define the stack and its use if
you are interested in more information on it.


WHAT IS THE HEAP?
____________________________________________________________

The heap is a Pascal defined entity that utilizes otherwise
unused memory to store data.  It begins immediately following
the program and grows as necessary upward toward the stack
which is growing downward.  As long as they never meet, there
is no problem.  If they meet, a run-time error is generated.
The heap is therefore outside of the 64K limitation of TURBO
Pascal and many other Pascal compilers.

TURBO Pascal version 4.0 or 5.x does not limit us to 64K, but
there are other reasons for using the heap in addition to the
64K limitation.  These should be evident as we learn how the
heap works.

If you did not understand the last few paragraphs, don't
worry.  Simply remember that dynamically allocated variables
are stored on the heap and do not count in the 64K limitation
placed upon you by some compilers.

Back to our example program, POINTERS.PAS.  When we actually
begin executing the program, we still have not defined the
variables we wish to use to store data in.  The first
executable statement in line 10 generates a variable for us
with no name and stores it on the heap.  Since it has no name,
we cannot do anything with it, except for the fact that we do
have a pointer My_Name that is pointing to it.  By using the
pointer, we can store up to 20 characters in it, because that
is its type, and later go back and retrieve it.


WHAT IS DYNAMIC ALLOCATION?
____________________________________________________________

The variable we have just described is a dynamically allocated
variable because it was not defined in a var declaration, but
with a New procedure.  The New procedure creates a variable
of the type defined by the pointer, puts it on the heap, and
finally assigns the address of the variable to the pointer
itself.  Thus My_Name contains the address of the variable
generated.  The variable itself is referenced by using the
pointer to it followed by a ^, just like in the last program,
and is read, "the variable to which the pointer points".



                                                    Page 12-4

                              Pointers and Dynamic Allocation

The statement in line 11 assigns a place on the heap to an
integer type variable and puts its address in My_Age.
Following the New statements we have two assignment statements
in which the two variables pointed at are assigned values
compatible with their respective types, and they are both
written out to the video display in much the same manner as
we did in the program named POINT.PAS.  This is illustrated
in figure 12-5.

Following execution of lines 13 and 14, the data space is
configured as illustrated in figure 12-6.


GETTING RID OF DYNAMICALLY ALLOCATED DATA
____________________________________________________________

The two statements in lines 19 and 20 are illustrations of the
way the dynamically allocated variables are removed from use.
When they are no longer needed, they are disposed of with the
Dispose procedure which frees up their space on the heap so
it can be reused.

In such a simple program, pointers cannot be appreciated, but
it is necessary for a simple illustration.  In a large, very
active program, it is possible to define many variables,
dispose of some of them, define more, and dispose of more,
etc.  Each time some variables are disposed of, their space
is then made available for additional variables defined with
the New procedure.
The heap can be made up of any assortment of variables, they
do not have to all be the same.  One point must be kept in
mind.  Anytime a variable is defined, it will have a pointer
pointing to it.  The pointer is the only means by which the
variable can be accessed.  If the pointer to the variable is
lost or changed, the data itself is lost for all practical
purposes.  Compile and run this program and examine the
output.


DYNAMICALLY STORING RECORDS;
____________________________________________________________

The next example program, DYNREC.PAS, is a   ================
repeat of one we studied in an earlier          DYNREC.PAS
chapter.  For your own edification, review   ================
the example program BIGREC.PAS before
going ahead in this chapter.  Assuming
that you are back in DYNREC.PAS, you will notice that this
program looks very similar to the earlier one, and in fact
they do exactly the same thing.  The only difference in the
type declaration is the addition of a pointer Person_Id, and
in the var declaration, the first four variables are defined
as pointers here, and were defined as record variables in the
last program.

                                                    Page 12-5

                              Pointers and Dynamic Allocation


A point should be made here.  Pointers are not generally used
in very small programs.  This program is a good bit larger
than the last and should be a clue to you as to why such a
trivial program was used to introduce pointers in this
tutorial.  A very small, concise program can illustrate a
topic much better that an large complex program, but we must
go on to more useful constructs of any new topic.


WE JUST BROKE THE GREAT RULE OF PASCAL
____________________________________________________________

Notice in the type declaration that we used the identifier
Person in line 18 before we defined it in line 19, which is
illegal to do in Pascal.  Foreseeing the need to define a
pointer prior to the record, the designers of Pascal allow us
to break the rule in this one place.  The pointer could have
been defined after the record in this particular case, but it
was more convenient to put it before, and in the next example
program, it will be required to put it before the record.  We
will get there soon.
Since Friend is really 50 pointers, we have now defined 53
different pointers to records, but so far have defined no
variables other than Temp and Index.  We immediately use the
New procedure to dynamically allocate a record with Self
pointing to it, and use the pointer so defined to fill the
dynamically allocated record.  Compare this to the program
named  BIGREC and you will see that it is identical except for
the addition of the New and adding the ^ to each use of the
pointer to designate the data pointed to.


THIS IS A TRICK, BE CAREFUL
____________________________________________________________

Now go down to line 48 where Mother is allocated a record and
is then pointing to the record.  It seems an easy thing to do
then to simply assign all of the values of self to all the
values of mother as shown in the next statement, but it
doesn't work.  All the statement does, is make the pointer
Mother point to the same place where Self is pointing because
we did a pointer assignment.  The data that was allocated to
the pointer Mother is now somewhere on the heap, but we don't
know where, and we cannot find it, use it, or deallocate it.
This is an example of losing data on the heap.  The proper way
is given in the next two statements where all fields of Father
are defined by all fields of Mother which is pointing at the
original Self record.  Note that since Mother and Self are
both pointing at the same record, changing the data with
either pointer results in the data appearing to be changed in
both because there is, in fact, only one field where the data
is stored.


                                                    Page 12-6

                              Pointers and Dynamic Allocation

In order to Write from or Read into a dynamically assigned
record it is necessary to use a temporary record since
dynamically assigned records are not allowed to be used in I/O
statements.  This is illustrated in lines 57 through 63 of the
program where some data is written to the monitor.

Finally, the dynamically allocated variables are disposed of
prior to ending the program.  For a simple program such as
this, it is not necessary to dispose of them because all
dynamic variables are disposed of automatically when the
program is terminated and we return to DOS or the TURBO Pascal
integrated environment.  Notice that if the "Dispose(Mother);"
statement was included in the program, the data could not be
found due to the lost pointer, and the program would be
unpredictable, probably leading to a system crash.

It would be a meaningful exercise for you to diagram the data
space for this program, at a few selected points in its
execution, in a manner similar to that done in figure 12-1 to
figure 12-5 of this chapter.


SO WHAT GOOD IS THIS ANYWAY?
____________________________________________________________

Remember when you were initially studying BIGREC.PAS?  I
suggested that you see how big you could make the constant
Number_Of_Friends before you ran out of memory.  At that time
we found that it could be made slightly greater than 1000
before we got the memory overflow message at compilation.  Try
the same thing with DYNREC.PAS to see how many records it can
handle, remembering that the records are created dynamically,
so you will have to run the program to actually run out of
memory.  The final result will depend on how much memory you
have installed, and how many memory resident programs you are
using such as "Sidekick".  If you have a full memory of 640K,
I would suggest you start somewhere above 8000 records of
Friend.

Now you should have a good idea of why Dynamic Allocation can
be used to greatly increase the usefulness of your programs.
There is, however, one more important topic we must cover on
dynamic allocation.  That is the linked list.


WHAT IS A LINKED LIST?
____________________________________________________________

Understanding and using a linked list is     ================
by far the most baffling topic you will        LINKLIST.PAS
confront in Pascal.  Many people simply      ================
throw up their hands and never try to use
a linked list.  I will try to help you
understand it by use of an example and lots of explanation.

                                                    Page 12-7

                              Pointers and Dynamic Allocation

Examine the program named LINKLIST.PAS for an example of a
linked list.  I tried to keep it short so you could see the
entire operation and yet do something meaningful.

To begin with, notice that there are two types defined in
lines 4 and 6, a pointer to the record and the record itself.
The record, however, has one thing about it that is new to us,
the last entry, Next is a pointer to another record of this
type.  This record then, has the ability to point to itself,
which would be trivial and meaningless, or to another record
of the same type which would be extremely useful in some
cases.  In fact, this is the way a linked list is used.  I
must point out, that the pointer to another record, in this
case called Next, does not have to be last in the list, it can
be anywhere it is convenient for you.

A couple of pages ago, we discussed the fact that we had to
break the great rule of Pascal and use an identifier before
it was defined.  This is the reason the exception to the rule
was allowed.  Since the pointer points to the record, and the
record contains a reference to the pointer, one has to be
defined after being used, and by rules of Pascal, the pointer
can be defined first, provided that the record is defined
immediately following it.  That is a mouthful but if you just
use the syntax shown in the example, you will not get into
trouble with it.


STILL NO VARIABLES?
____________________________________________________________

It may seem strange, but we still will have no variables
defined, except for our old friend Index.  In fact for this
example, we will only define 3 pointers.  In the last example
we defined 54 pointers, and had lots of storage room.  Before
we are finished, we will have at least a dozen pointers but
they will be stored in our records, so they too will be
dynamically allocated.

Lets look at the program itself now.  In line 20, we create
a dynamically allocated record and define it by the pointer
Place_In_List.  It is composed of the three data fields, and
another pointer.  We define Start_Of_List to point to the
first record created, and we will leave it unchanged
throughout the program.  The pointer Start_Of_List will always
point to the first record in the linked list which we are
building up.  The data space is as depicted in figure 12-7.


WHAT IS "nil" AND WHAT IS IT USED FOR?
____________________________________________________________

We define the three variables in the record to be any name we
desire for illustrative purposes, and set the pointer in the

                                                    Page 12-8

                              Pointers and Dynamic Allocation

record to nil.  The word nil is another reserved word that
doesn't give the pointer an address but defines it as empty.
A pointer that is currently nil cannot be used to manipulate
data because it has no value, but it can be tested in a
logical statement to see if it is nil.  It is therefore a
dummy assignment.  With all of that, the first record is
completely defined.


DEFINING THE SECOND RECORD
____________________________________________________________

When you were young you may have played a searching game in
which you were given a clue telling you where to find the next
clue.  The next clue had a clue to the location of the third
clue.  You kept going from clue to clue until you found the
prize.  You simply exercised a linked list.  We will now build
up the same kind of a list in which each record will tell us
where the next record is at.

In lines 27 through 33 we will define the second record.  Our
goal will be to store a pointer to the second record in the
pointer field of the first record.  In order to keep track of
the last record, the one in which we need to update the
pointer, we will keep a pointer to it in Temp_Place.  Now we
can dynamically allocate another New record and use
Place_In_List to point to it.  Since Temp_Place is now
pointing at the first record, we can use it to store the value
of the pointer which points to the new record which we do in
line 29.  The 3 data fields of the new record are assigned
nonsense data for our illustration, and the pointer field of
the new record is assigned nil.  We have reached the point
when the data space is as depicted in figure 12-8.

Let's review our progress to this point.  We now have the
first record with a person's name and a pointer to the second
record, and a second record with a different person's name and
a pointer assigned nil.  We also have three pointers, one
pointing to the first record, one pointing to the last record,
and one we used just to get here since it is only a temporary
pointer.  If you understand what is happening so far, let's
go on to add some additional records to the list.  If you are
confused, go back over this material again.


TEN MORE RECORDS
____________________________________________________________

The next section of code is contained within a for loop so the
statements are simply repeated ten times.  If you observe
carefully, you will notice that the statements are identical
to the second group of statements in the program (except of
course for the name assigned).  They operate in exactly the
same manner, and we end up with ten more names added to the

                                                    Page 12-9

                              Pointers and Dynamic Allocation

list.  You will now see why the temporary pointer was
necessary, but pointers are cheap, so feel free to use them
at will.  A pointer generally uses only 4 bytes of memory.


FINALLY, A COMPLETE LINKED LIST
____________________________________________________________

We now have generated a linked list of twelve entries.  We
have a pointer pointing at the first entry, and another
pointer pointing at the last.  The only data stored within the
program itself are three pointers, and one integer, all of the
data is on the heap.  This is one advantage to a linked list,
it uses very little local memory, but it is costly in terms
of programming.  (Keep in mind that all of the data must be
stored somewhere in memory, and in the case of the linked
list, it is stored on the heap.)  You should never use a
linked list simply to save memory, but only because a certain
program lends itself well to it.  Some sorting routines are
extremely fast because of using a linked list, and it could
be advantageous to use in a database.  Figure 12-9 is a
graphical representation of what the linked list looks like.


HOW DO WE GET TO THE DATA NOW?
____________________________________________________________

Since the data is in a list, how can we get a copy of the
fourth entry for example?  The only way is to start at the
beginning of the list and successively examine pointers until
you reach the desired one.  Suppose you are at the fourth and
then wish to examine the third.  You cannot back up, because
you didn't define the list that way, you can only start at the
beginning and count to the third.  You could have defined the
record with two pointers, one pointing forward, and one
pointing backward.  This would be a doubly-linked list and you
could then go directly from entry four to entry three.

Now that the list is defined, we will read the data from the
list and display it on the video monitor.  We begin by
defining the pointer, Place_In_List, as the start of the list.
Now you see why it was important to keep a copy of where the
list started.  In the same manner as filling the list, we go
from record to record until we find the record with nil as a
pointer.

There are entire books on how to use linked lists, and most
Pascal programmers will seldom, if ever, use them.  For this
reason, additional detail is considered unnecessary, but to
be a fully informed Pascal programmer, some insight is
necessary.




                                                   Page 12-10

                              Pointers and Dynamic Allocation

PROGRAMMING EXERCISE
____________________________________________________________

1.   Write a program to store a few names dynamically, then
     display the stored names on the monitor.  As your first
     exercise in dynamic allocation, keep it very simple.

















































                                                   Page 12-11